package STO_34;

import java.util.LinkedList;
import java.util.List;

import LCommon.TreeNode;

public class Solution {
	LinkedList<List<Integer>> ret = new LinkedList<>();
	LinkedList<Integer> path = new LinkedList<Integer>();

	public List<List<Integer>> pathSum(TreeNode root, int sum) {
		recur(root, sum);
		return ret;

	}

	private void recur(TreeNode root, int tar) {
		if (root == null) {
			return;
		}
		path.add(root.val);
		tar -= root.val;
		if (tar == 0 && root.left == null && root.right == null) {
			ret.add(new LinkedList<Integer>(path));
		}
		recur(root.left, tar);
		recur(root.right, tar);
		path.removeLast();
	}
}
